/* $Id: RoundCalculator.java 110 2009-05-28 20:57:15Z henk $ */
package org.jugger.tournament.model;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

import org.jugger.tournament.model.score.ScoreCalculator;

public class RoundCalculator {

	public static Round calculateRandomRound(ScoreCalculator scoreCalculator, Collection<Team> teams, HashMap<Team, HashSet<Team>> hasPlayedAgainst) {
		return calculateRound(scoreCalculator, teams, hasPlayedAgainst, null);
	}

	/**
	 * Calculates a new round based on done matches and currentRanking.
	 * @param scoreCalculator
	 * @param teams
	 * @param hasPlayedAgainst
	 * @param currentRanking
	 * @return
	 */
	public static Round calculateRound(ScoreCalculator scoreCalculator, Collection<Team> teams, HashMap<Team, HashSet<Team>> hasPlayedAgainst, Collection<TeamStats> currentRanking) {
		Round round = null;
		boolean randomize = currentRanking == null;

		if (randomize) {
			// first round => select random team pairs and create matches
			LinkedList<Team> teamsLeft = new LinkedList<Team>(teams);
			Random rnd = new Random();
			round = new Round();
			while (!teamsLeft.isEmpty()) {
				Team teamA = teamsLeft.remove(rnd.nextInt(teamsLeft.size()));
				Team teamB = teamsLeft.remove(rnd.nextInt(teamsLeft.size()));
				round.add(new Match(scoreCalculator, teamA, teamB));
			}
		} else {
			// not first round => select following team pairs

			LinkedList<Match> problemMatches = new LinkedList<Match>();
			LinkedList<Team> teamsOpen = new LinkedList<Team>();
			Stack<Match> calculatedMatches = new Stack<Match>();

			for(TeamStats ts: currentRanking) {
				if(teams.contains(ts.getTeam())) {
					teamsOpen.add(ts.getTeam());
				}
			}

			if(calculateRoundBacktracking(scoreCalculator, teamsOpen, hasPlayedAgainst, calculatedMatches, problemMatches)) {
				// paarungen gefunden
				round = new Round();
				for(Match m: calculatedMatches) {
					round.add(m);
				}
			}
			else {
				// no complete round possible :-(
				// instead use old algorithm => at least some matches should be "ok".

				round = calculateProblematicRound(scoreCalculator, teams, hasPlayedAgainst, currentRanking);
			}
		}

		return round;
	}

	public static Round calculateProblematicRound(ScoreCalculator scoreCalculator, Collection<Team> teams, HashMap<Team, HashSet<Team>> hasPlayedAgainst, Collection<TeamStats> currentRanking) {
		Round round = new Round();

		// get current teams from ranking (sorted!)
		LinkedList<Team> teamsLeft = new LinkedList<Team>();
		for(TeamStats teamStats: currentRanking) {
			// only, if team is in team-set
			if(teams.contains(teamStats.getTeam()))
				teamsLeft.add(teamStats.getTeam());
		}

		LinkedList<Team> teamsUnsolved = new LinkedList<Team>();
		while (!teamsLeft.isEmpty()) {
			Team teamA = teamsLeft.removeFirst();
			Set<Team> teamAOpponents = hasPlayedAgainst.get(teamA);
			Team teamB = null;

			// search for next team, that has not already played against
			// teamA
			for (Team team : teamsLeft) {
				if (!teamAOpponents.contains(team)) {
					// this team would fit
					teamB = team;
					teamsLeft.remove(team);
					break;
				}
			}

			if (teamB == null) {
				// no opponent team found!
				// add to unsolved
				teamsUnsolved.add(teamA);
			} else {
				// create match
				round.add(new Match(scoreCalculator, teamA, teamB));
			}
		}

		// bad resolving of problematic matches.
		while (!teamsUnsolved.isEmpty()) {
			Team teamA = teamsUnsolved.remove();
			Team teamB = teamsUnsolved.remove();
			round.add(new Match(scoreCalculator, teamA, teamB));
		}

		return round;
	}


	/*
	 * backtracking algorithm basics:
	 *
	 * EF = entscheidungsfolge
	 * falls EF Lösung ist
	 *      return true
	 * sonst
	 *      für alle jetzt möglichen Entscheidungen
	 *           falls Entscheidung nicht erkennbar falsch
	 *                verlängere Entscheidungsfolge EF um diese Entscheidung,
	 *                     (die verlängerte Entscheidungsfolge heiße EF')
	 *                BacktrackingRek(EF')
	 *
	 * konkret:
	 *
	 * EF = stack mit matches
	 * falls kein team mehr offen
	 *      return true
	 * sonst
	 *
	 *      nächste paarung erzeugen
	 *      erzeuge nächstes match
	 *
	 *
	 *
	 *
	 *
	 *
	 * Funktion FindeLoesung (Stufe, Vektor)
	 *   1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
	 *      a) wähle einen neuen Teil-Lösungsschritt;
	 *      b) falls Wahl gültig ist:
	 *                I) erweitere Vektor um Wahl;
	 *               II) falls Vektor vollständig ist, return true; // Lösung gefunden!
	 *         sonst:
	 *                   falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
	 *                   sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
	 *   2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!
	 *
	 */

	private static Match getPossibleMatch(ScoreCalculator scoreCalculator, LinkedList<Team> teamsOpen, HashMap<Team, HashSet<Team>> hasPlayedAgainst, List<Match> problemMatches) {

		for(Team teamA: teamsOpen) {
			for(Team teamB: teamsOpen) {

				// team nicht identisch?
				if(teamA != teamB) {

					// nicht gegeneinander gespielt?
					if(!hasPlayedAgainst.get(teamA).contains(teamB)) {

						// match ist nicht als problematisch markiert? (symmetrisch)
						boolean isPossible = true;
						for(Match m: problemMatches) {
							if(m.containsTeam(teamA) && m.containsTeam(teamB)) {
								isPossible = false;
								break;
							}
						}

						if(isPossible) {
							// match kann mal probiert werden
							return new Match(scoreCalculator, teamA, teamB);
						}

					}
				}

			}
		}

		// keine passende paarung gefunden! :-/
		return null;
	}

	/**
	 * Recursive backtracking algorithm to determine suitable matches (teams have not played against each other)
	 * @param scoreCalculator
	 * @param teamsOpen Teams left, that need a match in new round
	 * @param hasPlayedAgainst
	 * @param currentRanking
	 * @param calculatedRound Current calculated round, without problems (backtracking vector)
	 * @return true, if success (calculatedRound finished) on problem false
	 */
	private static boolean calculateRoundBacktracking(ScoreCalculator scoreCalculator, LinkedList<Team> teamsOpen, HashMap<Team, HashSet<Team>> hasPlayedAgainst, Stack<Match> calculatedMatches, LinkedList<Match> problemMatches) {

		// kein team mehr offen => yay
		if(teamsOpen.isEmpty())
			return true;

		Match possibleMatch = null;

		// ab hier auf eigener kopie arbeiten/ändern
		// wenn dieser pfad komplett versagt hat wird alles aus dem pfad hier "vergessen"
		problemMatches = new LinkedList<Match>(problemMatches);

		do {

			// suche mögliche neue paarung heraus
			possibleMatch = getPossibleMatch(scoreCalculator, teamsOpen, hasPlayedAgainst, problemMatches);
			if(possibleMatch != null) {

				calculatedMatches.push(possibleMatch);

				// teams erstmal nicht mehr offen
				LinkedList<Team> teamsOpenNext = new LinkedList<Team>(teamsOpen);
				teamsOpenNext.remove(possibleMatch.getTeamA());
				teamsOpenNext.remove(possibleMatch.getTeamB());

				// rekursiver abstieg mit possibleMatch
				if(calculateRoundBacktracking(scoreCalculator, teamsOpenNext, hasPlayedAgainst, calculatedMatches, problemMatches)) {
					// sauber. fertig! :D
					return true;
				}
				else {
					// hat nicht geklappt -> possibleMatch zurücknehmen und als problematic markieren
					problemMatches.add( calculatedMatches.pop() );
				}

				// nächstes match erzeugen
			}

		} while(possibleMatch != null);

		return false;
	}
}
